<!--
 * @Author: your name
 * @Date: 2021-07-27 13:50:26
 * @LastEditTime: 2021-07-27 17:56:57
 * @Description: 
-->
<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>图结构</title>
</head>

<body>
  <script src="dict.js"></script>
  <script src="queue.js"></script>
  <script>
    function Graph() {
      // 属性：顶点(数组)、边(字典)
      this.vertexes = [] // 顶点；白色：没有访问过；灰色：被访问过，但没探索过；黑色：被访问过且被完成探索过(关联的顶点被访问)
      this.edges = new Dictionary() // 边

      // 1. 添加顶点方法
      Graph.prototype.addVertex = function (v) {
        this.vertexes.push(v)
        this.edges.set(v, [])
      }

      // 2. 添加边
      Graph.prototype.addEdge = function (v1, v2) {
        this.edges.get(v1).push(v2)
        this.edges.get(v2).push(v1)
      }

      Graph.prototype.toString = function () {
        // 1. 定义字符串保存最终结果
        var resultString = ''

        // 2. 遍历所有的顶点，以及顶点对应的边
        for (var i = 0; i < this.vertexes.length; i++) {
          resultString += this.vertexes[i] + '->'
          var vEdges = this.edges.get(this.vertexes[i])
          for (var j = 0; j < vEdges.length; j++) {
            resultString += vEdges[j] + ' '
          }
          resultString += '\n'
        }
        return resultString
      }

      // 初始化状态颜色
      Graph.prototype.initializeColor = function () {
        var colors = []
        for (var i = 0; i < this.vertexes.length; i++) {
          colors[this.vertexes[i]] = 'white'
        }
        return colors
      }

      // 广度优先搜索（BFS）
      Graph.prototype.bfs = function (initV, handler) {
        // 1. 初始化颜色
        var colors = this.initializeColor()

        // 2. 创建队列
        var queue = new Queue()

        // 3. 将顶点加入到队列
        queue.enqueue(initV)

        // 4. 循环从队列中取出元素
        while (!queue.isEmpty()) {
          // 4.1 从队列取出一个顶点
          var v = queue.dequeue()

          // 4.2. 获取和顶点相连的另外顶点
          var vList = this.edges.get(v)

          // 4.3. 将v的颜色设置为灰色
          colors[v] = 'gray'

          // 4.4. 遍历所有的顶点，并且加入到队列
          for (var i = 0; i < vList.length; i++) {
            var e = vList[i]
            if (colors[e] === 'white') {
              colors[e] = 'gray'
              queue.enqueue(e)
            }
          }

          // 4.5. 访问顶点
          handler(v)

          // 4.6. 将顶点设置为黑色
          colors[v] = 'black'
        }
      }

      // 深度优先搜索（DFS）
      Graph.prototype.dfs = function (initV, handler) {
        // 1. 初始化颜色
        var colors = this.initializeColor()

        // 2. 从某个顶点开始依次递归访问
        this.dfsVisit(initV, colors, handler)
      }

      Graph.prototype.dfsVisit = function (v, colors, handler) {
        // 1. 将颜色设置为灰色
        colors[v] = 'gray'

        // 2. 处理v顶点
        handler(v)

        // 3. 访问v相连的顶点
        var vList = this.edges.get(v)
        for (var i = 0; i < vList.length; i++) {
          var e = vList[i]
          if (colors[e] === 'white') {
            this.dfsVisit(e, colors, handler)
          }
        }

        // 4. 将v设置为黑色
        colors[v] = 'black'
      }
    }

    var g = new Graph()
    var myVer = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
    myVer.forEach(i => {
      g.addVertex(i)
    })

    g.addEdge('A', 'B')
    g.addEdge('A', 'C')
    g.addEdge('A', 'D')
    g.addEdge('C', 'D')
    g.addEdge('C', 'G')
    g.addEdge('D', 'G')
    g.addEdge('D', 'H')
    g.addEdge('B', 'E')
    g.addEdge('B', 'F')
    g.addEdge('E', 'I')

    // alert(g)

    var result = ''
    g.dfs(g.vertexes[0], function (v) {
      result += v + ' '
    })
    alert(result)
  </script>
</body>

</html>